/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM73 最长回文子串
 * https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=295&tqId=25269&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-12
 * Time: 23:16
 */

//本解法是中心扩散法，除此之外还有动态规划法
//不过动态规划法的时间和空间复杂度都没有优化
//牛客网上面还有一个manacher算法，大大优化时间复杂度
//但是没看懂，后续可以继续琢磨，继续优化

import java.util.*;
//注意：本题中也可以不创建dp和dp1数组，直接利用maxLen进行记录，后续可以改进。
public class Solution {
    public int getLongestPalindrome(String A) {
        //题目中A的长度大于1，不需要判空处理
        int len = A.length();
        int maxLen = 0;  //记录最长回文子串的长度
        //当回文字串的长度为奇数的时候
        //dp[i]表示的是以A[i]作为中心字符的最长回文子串的长度
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            int left = i - 1;
            int right = i + 1;
            while (left >= 0 && right < len && A.charAt(left) == A.charAt(right)) {
                left--;
                right++;
            }
            dp[i] = right - left - 1;
            maxLen = Math.max(maxLen, dp[i]);
        }
        //当回文字串的长度为偶数的时候
        //dp[i]表示的是以A[i]和A[i+1]作为中心字符的最长回文子串的长度
        int[] dp1 = new int[len - 1];
        for (int i = 0; i < len - 1; i++) {
            int left = i;
            int right = i + 1;
            while (left >= 0 && right < len && A.charAt(left) == A.charAt(right)) {
                left--;
                right++;
            }
            dp1[i] = right - left - 1;
            maxLen = Math.max(maxLen, dp1[i]);
        }
        return maxLen;
    }
}